#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int uniquePaths(int m, int n) {
	vector<vector<int>> dp(m, vector<int>(n));
	for (int i = 0; i < m; i++) dp[i][0] = 1;
	for (int i = 0; i < n; i++) dp[0][i] = 1;
	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < n; j++)
		{
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[m - 1][n - 1];
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int m = obstacleGrid.size(), n = obstacleGrid[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	dp[0][1] = 1;
	for(int i=1;i<=m;i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (obstacleGrid[i][j] == 0)
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
	}
	return dp[m][n];
}
int jewelleryValue(vector<vector<int>>& frame) {
	int m = frame.size(), n = frame[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
		}
	}
	return dp[m][n];
}
int minFallingPathSum(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = matrix[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));
	for (int i = 0; i < n + 2; i++)
		dp[0][i] = 0;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))
				+ matrix[i][j];
		}
	}
	int ret = INT_MAX;
	for (int i = 1; i <= n; i++)
	{
		ret = min(ret, dp[m][i]);
	}
	return ret;
}
int minPathSum(vector<vector<int>>& grid) {
	int m = grid.size(), n = grid[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1,INT_MAX));
	dp[0][1] = 0;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
		}
	}
	return dp[m][n];
}
int calculateMinimumHP(vector<vector<int>>& dungeon) {
	int m = dungeon.size(), n = dungeon[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1,INT_MAX));
	dp[m][n - 1] = 1;
	for (int i = m - 1; i >= 0; i--)
	{
		for (int j = n - 1; j >= 0; j--)
		{
			dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + dungeon[i][j];
			dp[i][j] = max(1, dp[i][j]);
		}
	}
	return dp[0][0];
}
int main()
{

	return 0;
}